#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣85. 最大矩形
// 【难度】困难
// 【提交】2025.9.18 https://leetcode.cn/problems/maximal-rectangle/submissions/664042379/
// 【标签】单调栈；动态规划；数组
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int m = matrix.size(), n = matrix[0].size();
        vector<int> heights(n + 1, 0);
        heights[n] = -1;
        int ans = 0;
        stack<int> stk; 
        stk.push(-1);
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                heights[j] = (matrix[i][j] == '1' ? heights[j] + 1 : 0);
            }
            ans = max(ans, maxRect(heights, stk));
        }
        return ans;
    }

    int maxRect(vector<int>& heights, stack<int>& stk) {
        int ans = 0;
        if (stk.top() != -1) {
            while (!stk.empty()) stk.pop();
            stk.push(-1);
        }
        for (int i = 0; i < heights.size(); ++i) {
            while (stk.top() != -1 && heights[stk.top()] > heights[i]) {
                int height = heights[stk.top()];
                stk.pop();
                int width = i - stk.top() - 1;
                ans = max(ans, height * width);
            }
            stk.push(i);
        }
        
        while (stk.top() != -1) {
            stk.pop();
        }
        return ans;
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一个二维二进制矩阵，找出只包含1的最大矩形，并返回其面积。
 * 模型：动态规划+单调栈，将二维问题转化为多个一维柱状图最大矩形问题。
 * 
 * 二、标准解法状态设计
 * 1. 逐行处理：将每一行视为柱状图的基底，计算每个位置上方连续1的高度。
 * 2. 对每一行，使用单调栈计算当前高度数组的最大矩形面积（类似LC84的解法）。
 * 3. 使用哨兵技巧简化边界处理。
 * 
 * 三、你的实现思路
 * 使用动态规划方法逐行构建高度数组，然后对每一行应用LC84的解法求出最大矩形面积。
 * 通过复用栈对象减少内存分配开销。
 * 
 * 四、逐行注释（带细节提醒）
 * vector<int> heights(n + 1, 0); // 高度数组，多一个元素作为哨兵
 * heights[n] = -1; // 哨兵值，确保最后所有元素都能被弹出
 * stack<int> stk; // 单调栈，存储索引
 * stk.push(-1); // 初始边界
 * 
 * for (int i = 0; i < m; ++i) { // 逐行处理矩阵
 *     for (int j = 0; j < n; ++j) { // 更新当前行的高度数组
 *         if (matrix[i][j] == '1') {
 *             heights[j] += 1; // 连续1的高度增加
 *         } else {
 *             heights[j] = 0; // 遇到0，高度重置
 *         }
 *     }
 *     ans = max(ans, maxRect(heights, stk)); // 计算当前行的最大矩形面积
 * }
 * 
 * // maxRect函数：计算柱状图中的最大矩形面积
 * int maxRect(vector<int>& heights, stack<int>& stk) {
 *     int ans = 0;
 *     if (stk.top() != -1) { // 确保栈的初始状态正确
 *         while (!stk.empty()) stk.pop();
 *         stk.push(-1);
 *     }
 *     
 *     for (int i = 0; i < heights.size(); ++i) { // 遍历所有高度（包括哨兵）
 *         while (stk.top() != -1 && heights[stk.top()] > heights[i]) { // 维护单调递增栈
 *             int height = heights[stk.top()]; // 当前柱子的高度
 *             stk.pop();
 *             int width = i - stk.top() - 1; // 计算宽度
 *             ans = max(ans, height * width); // 更新最大面积
 *         }
 *         stk.push(i); // 将当前索引入栈
 *     }
 *     
 *     while (stk.top() != -1) { // 恢复栈的初始状态
 *         stk.pop();
 *     }
 *     return ans;
 * }
 * 
 * 五、正确性证明
 * 逐行构建高度数组，将二维问题转化为多个一维柱状图最大矩形问题。
 * 使用单调栈可以正确计算每个柱状图的最大矩形面积，哨兵技巧简化了边界处理。
 * 算法保证了每个元素只入栈和出栈一次，正确性由单调栈性质保证。
 * 
 * 六、复杂度
 * 时间：O(m×n)，每行处理需要O(n)时间，总共m行。
 * 空间：O(n)，高度数组和栈各需要O(n)空间。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 空间复杂度低，只需O(n)额外空间；
 *   - 代码结构清晰，易于理解；
 *   - 复用栈对象减少内存分配开销。
 * 缺点：
 *   - 需要多次调用maxRect函数，有一定函数调用开销；
 *   - 哨兵技巧可能对初学者不易理解。
 * 
 * 八、改进建议
 * 1. 可以将maxRect函数内联以减少函数调用开销；
 * 2. 使用更明确的变量名（如 heightArray 代替 heights）来增强可读性；
 * 3. 对于教学场景，可以添加注释解释哨兵的作用；
 * 4. 可以考虑使用数组代替栈，进一步提高性能。
 * 
 * 九、一句话总结
 * 通过逐行构建高度数组和应用单调栈技巧，将二维最大矩形问题转化为多个一维问题，
 * 你的实现空间效率高且代码清晰，展现了优化空间复杂度的能力。
 */